#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<unordered_set>
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len, 1);
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (nums[j] > nums[i]) {
                    dp[j] = max(dp[i] + 1, dp[j]);
                }
            }
        }
        int maxn = 0;
        for (auto& e : dp) {
            maxn = max(maxn, e);
        }
        return maxn;
    }
};

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        vector<int> tmpArr(nums.size() - 1);
        int len = tmpArr.size();
        vector<int> dp(len, 1);
        for (int i = 1; i < nums.size(); i++) {
            tmpArr[i - 1] = nums[i] - nums[i - 1];
        }
        if (len > 0 && tmpArr[0] == 0)dp[0] = 0;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (tmpArr[i] > 0 && tmpArr[j] < 0) {
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
                else if (tmpArr[i] < 0 && tmpArr[j] > 0) {
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
                else if (tmpArr[i] == 0) {
                    dp[i] = 0;
                    break;
                }
            }
        }
        int maxn = 0;
        for (auto& e : dp) {
            maxn = max(maxn, e);
            cout << e << " ";
        }
        return maxn + 1;
    }
};

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len, 1);
        vector<int> rem(len, 1);
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        rem[i] = rem[j];
                        dp[i] = dp[j] + 1;
                    }
                    else if (dp[j] + 1 == dp[i]) {
                        rem[i] += rem[j];
                    }
                }
            }
        }
        int max_digit = INT_MIN;
        for (auto& e : dp) {
            max_digit = max(e, max_digit);
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            if (max_digit == dp[i]) {
                ans += rem[i];
            }
        }
        return ans;
    }
};

class Solution {
public:

    struct MyCompare
    {
        bool operator()(const vector<int>& p1, const vector<int>& p2)
        {
            if (p1[0] < p2[0]) return true;
            else if (p1[0] == p2[0] && p1[1] < p2[1]) return true;
            else return false;
        }
    };

    int findLongestChain(vector<vector<int>>& pairs) {
        int len = pairs.size();
        sort(pairs.begin(), pairs.end(), MyCompare());
        vector<int> dp(len, 1);
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        int ans = 0;
        for (auto& e : dp) {
            ans = max(ans, e);
        }
        return ans;
    }
};

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int len = arr.size();
        vector<int> dp(len, 1);
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] - arr[j] == difference) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        int ans = 0;
        for (auto& e : dp) {
            ans = max(ans, e);
        }
        return ans;
    }
};

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int len = arr.size();
        // vector<int> dp(len, 1);
        unordered_map<int, int> hash;
        if (difference == 0) {
            for (auto& e : arr) {
                hash[e]++;
            }
            int ans = 0;
            for (auto& e : hash) {
                ans = max(ans, e.second);
            }
            return ans;
        }
        hash[arr[0]] = 1;
        for (int i = 1; i < len; i++) {
            if (hash.count(arr[i]) == 0) {
                hash[arr[i]] = 1;
            }
            if (hash.count(arr[i] - difference)) {
                hash[arr[i]] = max(hash[arr[i]], hash[arr[i] - difference] + 1);
            }
        }
        int ans = 0;
        for (auto& e : hash) {
            ans = max(ans, e.second);
        }
        return ans;
    }
};

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        unordered_set<int> hash;
        hash.reserve(70);
        long long a = 0, b = 1, c = 1;
        hash.insert(0);
        hash.insert(1);
        while (c < INT_MAX) {
            hash.insert(c);
            a = b;
            b = c;
            c = a + b;
            if (c < 50) {
                cout << c << " ";
            }
        }
        int len = arr.size();
        vector<int> dp(len, 0);
        for (int i = 0; i < len; i++) {
            if (hash.count(arr[i])) {
                dp[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (hash.count(arr[j])) {
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
            }
        }
        int ans = 0;
        for (auto& e : dp) {
            ans = max(ans, e);
            cout << e << " ";
        }
        return ans;
    }
};

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int len = arr.size();
        if (len < 2) {
            return 0;
        }
        unordered_map<int, int> hash;
        hash.reserve(100);
        vector<int> dp(len, 1);
        hash[arr[0]] = 1; hash[arr[1]] = 1;
        for (int i = 2; i < len; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] < arr[i] - arr[j]) break;
                if (hash.count(arr[i] - arr[j])) {
                    dp[i] = max(dp[i], hash[arr[i] - arr[j]] + 2);
                    if (hash[arr[i] - arr[j]] + 2 == 7) {
                        cout << arr[i] << " " << arr[j] << endl;;
                    }
                }
            }
            hash[arr[i]] = dp[i];
        }
        int ans = 0;
        for (auto& e : dp) {
            ans = max(ans, e);
            cout << e << " ";
        }
        return ans;
    }
};

// 2,4,5,6,7,8,11,13,14,15,21,22,34
// 1 1 1 3 3 3 3  5  5  5  5  5  7 

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int len = arr.size();
        vector<vector<int>> dp(len, vector<int>(len, 2));
        unordered_map<int, int> hash;
        hash[arr[0]] = 0;
        hash[arr[1]] = 1;
        for (int j = 2; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (hash.count(arr[j] - arr[i])) {
                    int k = hash[arr[j] - arr[i]];
                    if (arr[k] < arr[i])
                        dp[i][j] = max(dp[i][j], dp[k][i] + 1);
                }
            }
            hash[arr[j]] = j;
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                ans = max(ans, dp[i][j]);
            }
        }
        if (ans == 2)
            return 0;
        else
            return ans;
    }
};

